1. Field of the Invention
The present invention relates generally to an apparatus that provides error correction for encoded digital communications. More particularly, the invention is an analog device employing the architecture of a high order neural network model that operates in continuous space as a dynamical system for reliably achieving error correction of conventionally encoded digital communications with significantly lower error rates.
2. Description of the Prior Art
The use of error-correcting codes for the reliable transmission of digital information is commonplace in most communication systems. One conventional way to achieve an error-correction capability is to add certain number of extra bits to the actual information bits in a way that maximizes the Hamming distance between the code words. The resulting minimum Hanuning distance "d" of such a (binary) block code, which is the minimum number of bits in which all pairs of words differ, is a key property of the code. Specifically, a code is capable of correcting up to "t" errors in any received word if d.gtoreq.2t+1. For example, in a Hamming (7,4) code, the number of information bits is 4 and the number of transmitted bits is 7. The extra transmitted bits allow the separation between the 2.sup.4 possible meaningful data so that if some of the bits are corrupted, the result will not be too far away from the original to be found. In the Hamming (7,4) code, the minimum distance between meaningful data is 3 so that all pairs of transmitted codes differ by at least three bits. If one bit is corrupted during transmission, it is still easy to recover the original by finding the closest match (nearest Euclidean or Hamming neighbor) in a table of valid codes.
Another popular error correction code is the Hadamard nonlinear code where the distance between the codes is larger and thus has a greater corruption resistance.
Presently, to achieve decoding and possible error-correction of these types of codes, a "hard-decision" type decoding technique utilizing conventional, linear algebraic decoding algorithms may be employed. This technique requires a thresholding of the incoming noisy, analog signal in order to obtain binary values of the incoming signal. Specifically, the thresholding technique requires that each of the bits in the received string of "n" bits be rounded to a 1 or 0, before any decoding algorithm is used. In the process of rounding, some potentially useful information about the original string is lost.
A "soft-decision" type decoding technique operates with the incoming signal directly and results in improved error-correction capability.
Other types of coding techniques, such as convolutional codes, which are based on a different principle than block codes, can be combined with decoding techniques that allow soft-decision decoding. However, those techniques involve increased computational complexity that is prohibitive for certain applications.
As discussed in the article entitled "Code Recognition with Neural Network Dynamical Systems" by C. Jeffries, Society for Industrial and Applied Mathematics Review, Volume 32, No. 4, December 1990, a class of dynamical systems called neural networks can serve as a fully analog computer to simulate some aspect of cognition. More specifically, one type of mathematical neural network model is an n-dimensional difference equation or differential equation dynamical system that accounts for the dynamics of n neurons. Each neuron is mathematically a state x.sub.i (a real number) with an associated output g.sub.i =g.sub.i (x.sub.i), typically a ramp or sigmoidal gain function g.sub.i (x.sub.i). The time rate of change of x.sub.i is determined by a system function dependent on x.sub.i itself and the outputs of g.sub.i (x.sub.i). Thus, the purpose of the model is to exhibit dynamics analogous to image recognition, learning, limb control, or some other function of a central nervous system.
In the context of code recognition and error correction of data, a neural network can be used to simulate memory retrieval. As discussed in the C. Jeffries article, the time evolution of a trajectory of such a system is mathematical "recognition", meaning convergence to one of several "attractors" referred to as mathematical memories. The attractors are prespecified constant trajectories or limit cycles and mathematical recognition amounts to regarding an input binomial n-string with component values ranging from .+-.1 as an initial state of a trajectory, and observing the subsequent convergence of that trajectory to one of the memories. A model with such dynamics is said to have "content-addressable memory" because partial or imperfect knowledge of a memory leads to complete retrieval of the memory through system dynamics. Thus, the principle of operation of content-addressable memories is pattern completion or pattern correction, that is, the retrieval of a stored pattern that best fits an input pattern which is distorted or contains incomplete information. This is equivalent to decoding error-correcting binary codes if the code words are memories stored in the neural network and the inputs to the network are the analog estimates of data transmitted over a noisy channel. After presentation of this analog vector representing an initial value, the neural network as a dynamical system should then ideally converge to the closest attractor and produce the stored code word at its output, thus, performing soft-decision decoding.
For a successful application of a neural network to perform as a content-addressable memory, the neural network has to be capable of storing arbitrary words, and it has to be guaranteed that the stored words represent the only stable attractors of the memory. The limited success in using neural networks for this application can be attributed to the limitations of current models, which do not allow the storage of arbitrary words, have a limited memory capacity, and cannot guarantee that the stored patterns constitute the only attractors of the dynamical system.
Other disadvantages include the large number of electronic devices that must be included in order to provide error correction of larger encoded data words and the difficulty in implementing such a neural network in a monolithic chip.